package algorithm.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class LeetCode_514_findRotateSteps {
    public int findRotateSteps(String ring, String key) {
        char[] r = ring.toCharArray();
        char[] k = key.toCharArray();
        int rlen = r.length, klen = k.length;
        //dp[i] 代表在 ring 中走到 key[i] 单词位置所需的最短路径，
        //因 ring 中可能存在多个 key[i]，用 dp[i][j] 保存到每一个 key[i] 的最短路径
        int[][] dp = new int[klen][100];
        //记录 ring 中每个字母出现的位置（相同字母也分别记录）
        Map<Character, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < rlen; ++i) {
            List<Integer> list = map.getOrDefault(r[i], new ArrayList<>());
            list.add(i);
            map.put(r[i], list);
        }
        //记录 ring 中出现的所有 key[0] 单词的最短路径
        List<Integer> list0 = map.get(k[0]);
        for (int i = 0; i < list0.size(); ++i) {
            int x = list0.get(i);
            // 最短路径为正向到达和反向到达的最小值，1为按下按钮
            dp[0][i] = Math.min(x, rlen - x) + 1;
        }
        for (int i = 1; i < klen; ++i) {
            List<Integer> listNow = map.get(k[i]);
            List<Integer> listPre = map.get(k[i - 1]);
            for (int j = 0; j < listNow.size(); ++j) {
                int x = listNow.get(j);
                int tempMax = Integer.MAX_VALUE;
                for (int n = 0; n < listPre.size(); ++n) {
                    int y = listPre.get(n);
                    //第 n 个 key[i-1] 单词位置通过正向或反向到达第 j 个 key[i] 的最小距离
                    dp[i][j] = Math.min(rlen - Math.abs(x - y), Math.abs(x - y)) + 1 + dp[i - 1][n];
                    tempMax = Math.min(tempMax, dp[i][j]);
                }
                dp[i][j] = tempMax;
            }
        }
        int res = Integer.MAX_VALUE;
        // 最终结果为到达最后一个单词的最短路径 dp[klen-1][*] 中的最小值
        for (int i = 0; i < dp[0].length; ++i) {
            if (dp[klen - 1][i] == 0) {
                break;
            }
            res = Math.min(res, dp[klen - 1][i]);
        }
        return res;
    }

    public static void main(String[] args) {
        String ring = "godding", key = "gd";
        LeetCode_514_findRotateSteps leetCode_514_findRotateSteps = new LeetCode_514_findRotateSteps();
        System.out.println(leetCode_514_findRotateSteps.findRotateSteps(ring, key));

    }
}
